//
// Description: 5798. 循环轮转矩阵
// Created by Loading on 2021/6/27.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> rotateGrid(vector<vector<int>> &grid, int k) {
    int m = grid.size();
    int n = grid[0].size();
    //层数
    int layers = min(m / 2, n / 2);

    /* 模拟循环轮转 */
    for (int layer = 0; layer < layers; ++layer) {
        //记录每个元素的 行下标、列下表、元素值
        vector<int> row, col, val;
        //逆时针遍历四个方位，从第一个遍历至倒数第二个，四个方位元素个数相同
        //左侧
        for (int i = layer; i < m - layer - 1; ++i) {
            row.emplace_back(i);
            col.emplace_back(layer);
            val.emplace_back(grid[i][layer]);
        }
        //下侧
        for (int i = layer; i < n - layer - 1; ++i) {
            row.emplace_back(m - layer - 1);
            col.emplace_back(i);
            val.emplace_back(grid[m - layer - 1][i]);
        }
        //右侧
        for (int i = m - layer - 1; i > layer; --i) {
            row.emplace_back(i);
            col.emplace_back(n - layer - 1);
            val.emplace_back(grid[i][n - layer - 1]);
        }
        //上侧
        for (int i = n - layer - 1; i > layer; --i) {
            row.emplace_back(layer);
            col.emplace_back(i);
            val.emplace_back(grid[layer][i]);
        }

        //val 元素个数即为一轮回所需次数，用 k 对其取余，为有效的移动次数
        int rotate = k % val.size();
        for (int i = 0; i < val.size(); ++i) {
            //利用 val 数组辅助旋转，为旋转后的位置赋值
            grid[row[i]][col[i]] = val[(i - rotate + val.size()) % val.size()];
        }
    }

    return grid;
}

int main() {
    vector<vector<int>> grid = {{1,  2,  3,  4},
                                {5,  6,  7,  8},
                                {9,  10, 11, 12},
                                {13, 14, 15, 16}};
    int k = 2;
    vector<vector<int>> res = rotateGrid(grid, k);
    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
}